package leetcode.todo

import kotlinetc.println

/**
You have k lists of sorted integers in ascending order. Find the smallest range that includes at least one number from
each of the k lists.

We define the range [a,b] is smaller than range [c,d] if b-a < d-c or a < c if b-a == d-c.

Example 1:
Input:[[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
Output: [20,24]
Explanation:
List 1: [4, 10, 15, 24,26], 24 is in range [20,24].
List 2: [0, 9, 12, 20], 20 is in range [20,24].
List 3: [5, 18, 22, 30], 22 is in range [20,24].
Note:
The given list may contain duplicates, so ascending order means >= here.
1 <= k <= 3500
-105 <= value of elements <= 105.
For Java users, please note that the input type has been changed to List<List<Integer>>. And after you reset the code template, you'll see this point.
 */
fun main(args: Array<String>) {

    val testcase1 = listOf(
            listOf(4, 10, 15, 24, 26),
            listOf(0, 9, 12, 20),
            listOf(5, 18, 22, 30)
    )
    val testcase2 = listOf(listOf(1))
    smallestRangeVersion1(testcase2).asList().println()
}

/**
 * 提取出所有list的第一个 获得集合A，以及最后一个获得集合B。
 * 在A中移动左指针，同时保证 当前值要比B中的最小值要小
 * 在B中移动右指针，同时保证当前值要比A中最大值要大
 *
 * 当以上连个条件都不满足的时候 就知道
 * 。。。。。由于区间不是连续的，此方法行不通。。。考虑使用和[minwindowVersion1] 一样的思路
 * 即每个list中的数都至少出现一次
 */
fun smallestRange(nums: List<List<Int>>): IntArray {

    var l = 0
    var r = 0


    val A = nums.map { it.first() }.toIntArray()

    val AminIndex = A.indexOf(A.min()!!)

    val AmaxIndex = A.indexOf(A.max()!!)

    val B = nums.map { it.last() }.toIntArray()

    val BminIndex = B.indexOf(B.min()!!)
    val BmaxIndex = B.indexOf(B.max()!!)


    var leftBoundary = nums[BminIndex].last()
    var rightBoundary = nums[AmaxIndex].first()
    /**
     *            end
     *              ___________________
     *  ______
     *      start         ________
     */
    if (nums[BminIndex].last() <= nums[AmaxIndex].first()) return intArrayOf(nums[BminIndex].last(), nums[AmaxIndex].first())

    var leftList = nums[AmaxIndex]
    var rightList = nums[BminIndex]

    var i = 0
    var j = rightList.lastIndex

    /**
     *                               start   end
     *       ———————————————————————————————
     *             ——————————————————————————————————————————
     *         ————————————————————————————————
     *                   ————————————————————————————————————————————
     *    or here     start  end
     *
     *
     */

    leftBoundary = nums[BminIndex].last()
    rightBoundary = nums[AmaxIndex].first()

    while (rightList[j] > rightBoundary) {
        //优先从右往左边找
        j--
    }
    j++

    println("${rightBoundary} ${rightList[j]}")
    l = rightBoundary
    r = rightBoundary
    //然后从左边往右边找
    while (leftList[i] < leftBoundary) {
        i++
    }
    i--

    println("${leftList[i]} $leftBoundary")

    if (leftBoundary - leftList[i] < r - l) {
        l = leftList[i]
        r = leftBoundary
    } else if (leftBoundary - leftList[i] == r - l) {
        if (leftList[i] < l) {
            l = leftList[i]
            r = leftBoundary
        }
    }

    return intArrayOf(l, r)
}


/**
 * 整合数组，排序，但是在此之前先记录每个数字在原nums中是第几组。
 * 每有一个数字出现在一个新组，计数自增，直到计数等于nums数组大小
 */
fun smallestRangeVersion1(nums: List<List<Int>>): IntArray {

    var l = 0
    var r = 0
    var zippedNumberPairs = ArrayList<Pair<Int, Int>>()

    val size = nums.size
    var table = Array(size) { 0 }
    nums.forEachIndexed { index, list ->

        list.forEach { it ->
            zippedNumberPairs.add(Pair(index, it))
        }
    }
    zippedNumberPairs.sortBy { it.second }

    var bestL = -1
    var bestR = 0
    var count = 0
    val pairSize = zippedNumberPairs.size
    for (i in 0 until pairSize) {
        val index = zippedNumberPairs[i].first

        if (table[index] == 0) {
            count++

        }
        table[index]++

        r = i

        while (count == size && l <= r) {

            val right = zippedNumberPairs[r].second
            val left = zippedNumberPairs[l].second
            if (bestL == -1 || right - left < bestR - bestL) {
                bestL = left
                bestR = right
            }

            table[zippedNumberPairs[l].first]--
            if (table[zippedNumberPairs[l].first] == 0) count--

            l++
        }

    }
    return intArrayOf(bestL, bestR)
}

